
//152.乘积最大子数组
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();

        vector<int> f(n+1) , g(n+1);       //f记录乘积最大的值,g记录乘积最小的值
        f[0] = g[0] = 1;
        int ret = INT_MIN;
        for(int i = 1; i < n + 1; i++)
        {
            f[i] = max(max(f[i-1]*nums[i-1] , g[i-1]*nums[i-1]),nums[i-1]);
            g[i] = min(min(f[i-1]*nums[i-1] , g[i-1]*nums[i-1]),nums[i-1]);
            ret = max(ret,f[i]);
        }
        return ret;
    }
};